/*
 * @Description: 
 * @Author: Zilu
 * @Date: 2021-11-06 21:34:53
 * @Version: 
 * @LastEditTime: 2021-11-08 13:00:43
 * @LastEditors: Zilu
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node
{
    int value;
    struct node *left;
    struct node *right;
}binarytree;

long numberSum(binarytree *T);
binarytree *binarytreeGenerate(int n);
binarytree *getNode();
void insertNode(binarytree *T, binarytree *node);
void printBinarytree(binarytree *T);

int main(int argc, char const *argv[])
{
	binarytree *root = binarytreeGenerate(40);
	printBinarytree(root);
	int sum = numberSum(root);
	printf("\nThe sum of the tree is: %ld\n", sum);

	return 0;
}

//求所有节点的值
long numberSum(binarytree* T){
	long sum = 0L;
	if (T->left != NULL){
		sum += numberSum(T->left);
	}
	sum += T->value;
	if (T->right != NULL){
		sum += numberSum(T->right);
	}

	return sum;
}

//生成一个节点数为n的二叉树
binarytree* binarytreeGenerate(int n){
	if (n <= 0)
		return NULL;
	binarytree *root = getNode();	//根节点
	root->value = 50;		//随便设置的，方便平衡
	srand((unsigned)time(NULL));	//获取随机种子
	for (int i = 0; i < n-1; i++)
	{
		binarytree *newNode = getNode();
		insertNode(root, newNode);
	}
	return root;
}

//获取一个新节点
binarytree* getNode(){
	binarytree *T = (binarytree *)malloc(sizeof(binarytree));
	T->value = rand() % 100;		//初值为100以内一个随机的数
	T->left = NULL;	
	T->right = NULL;
	return T;
}

//插入一个节点
void insertNode(binarytree* T, binarytree* node){
	// 小于的值放左边，大于的值放右边
	if (node->value < T->value){
		if (T->left == NULL){
			T->left = node;
		} else{
			insertNode(T->left, node);
		}
	} else {
		if (T->right == NULL){
			T->right = node;
		} else{
			insertNode(T->right, node);
		}
	}
}

//输入二叉树所有的节点值
void printBinarytree(binarytree* T){
	if (T->left != NULL){
		printBinarytree(T->left);
	}
	printf("%4d", T->value);
	if (T->right != NULL){
		printBinarytree(T->right);
	}
}

